package com.future;

import java.lang.*;
import java.util.*;

/**
 * Description:
 * 电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。
 * <p>
 * 给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。
 * <p>
 * 最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/freedom-trail
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/3/22:22:48
 */
public class Solution_findRotateSteps_514 {

    public static void main(String[] args) {

        String ring = "godding", key = "gd";
        key = "godding";
        int s = findRotateSteps(ring, key);
        int s2 = findRotateSteps_dp(ring, key);
        System.out.println(s);
        System.out.println(s2);
    }


    /**
     * 暴力
     *
     * @param ring
     * @param key
     * @return
     */
    public static int findRotateSteps_dp(String ring, String key) {
        if (ring == null || ring.length() == 0) {
            return 0;
        }
        Map<Character, List<Integer>> map = new HashMap<>();
        char[] chars = ring.toCharArray();
        int N = chars.length;
        for (int i = 0; i < N; i++) {
            if (!map.containsKey(chars[i])) {
                map.put(chars[i], new ArrayList<>());
            }
            map.get(chars[i]).add(i);
        }
        char[] keyChars = key.toCharArray();
        int M = keyChars.length;
        int[][] dp = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dp[i][j] = -1;
            }
        }
        return process_dp(keyChars, 0, 0, chars.length, map, dp);
    }

    private static int process_dp(char[] keyChars, int preIndex, int curIndex, int N, Map<Character, List<Integer>> map, int[][] dp) {
        if (curIndex == keyChars.length) {
            return 0;
        }
        if (dp[preIndex][curIndex] != -1) {
            return dp[preIndex][curIndex];
        }
        int ans = Integer.MAX_VALUE;
        List<Integer> list = map.get(keyChars[curIndex]);
        for (Integer cur : list) {
            int v1 = call(preIndex, cur, N) + 1 + process_dp(keyChars, cur, curIndex + 1, N, map, dp);
            ans = Math.min(ans, v1);
        }
        dp[preIndex][curIndex] = ans;
        return ans;
    }

    /**
     * 暴力
     *
     * @param ring
     * @param key
     * @return
     */
    public static int findRotateSteps(String ring, String key) {
        if (ring == null || ring.length() == 0) {
            return 0;
        }
        Map<Character, List<Integer>> map = new HashMap<>();
        char[] chars = ring.toCharArray();
        /**
         * 记录ring中每个字符出现的下标
         */
        for (int i = 0; i < chars.length; i++) {
            if (!map.containsKey(chars[i])) {
                map.put(chars[i], new ArrayList<>());
            }
            map.get(chars[i]).add(i);
        }
        char[] keyChars = key.toCharArray();
        return process(keyChars, 0, 0, chars.length, map);
    }

    private static int process(char[] keyChars, int preIndex, int curIndex, int N, Map<Character, List<Integer>> map) {
        if (curIndex == keyChars.length) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        List<Integer> list = map.get(keyChars[curIndex]);
        for (Integer cur : list) {
            int v1 = call(preIndex, cur, N) + 1 + process(keyChars, cur, curIndex + 1, N, map);
            ans = Math.min(ans, v1);
        }
        return ans;
    }

    /**
     * 环形中，假设点A和点B在环上，则AB间连接有两条路径，顺着和逆着都能连通，求最短的
     *
     * @param preIndex
     * @param curIndex
     * @param N
     * @return
     */
    private static int call(int preIndex, int curIndex, int N) {
        return Math.min(Math.abs(preIndex - curIndex), N + Math.min(preIndex, curIndex) - Math.max(preIndex, curIndex));
    }

}
